/*
	解法：虚拟头结点 + 三个指针
	为什么：三个指针分别保存：当前正在处理的一对节点前面的那个节点，要交换的两个节点
	时间复杂度：O(n)，空间复杂度：O(1)
 */


#include <iostream>
#include <vector>

using namespace std;

// 定义链表节点结构
struct ListNode
{
	int val;
	ListNode* next;
	
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
	ListNode* swapPairs(ListNode* head)
	{
		ListNode* dummy = new ListNode(-1);
		dummy->next = head;
		
		ListNode* prev = dummy;		//指向当前正在处理的一对节点前面的那个节点
		
		while (prev->next != nullptr && prev->next->next != nullptr)	//对应偶数个节点和奇数个节点的终止条件
		{
			ListNode* first = prev->next;		//当前要交换的第一个节点
			ListNode* second = first->next;		//当前要交换的第二个节点
			
			// 交换节点
			prev->next = second;
			first->next = second->next;
			second->next = first;
			
			// 前进两个节点
			prev = first;
		}
		
		ListNode* newHead = dummy->next;		//dummy->next 在第一轮 while 中被修改了
		delete dummy;
		return newHead;
	}
};

// 辅助函数：根据 vector 构建链表
ListNode* buildList(const vector<int>& nums)
{
	ListNode* dummy = new ListNode(-1);
	ListNode* tail = dummy;
	
	for (size_t i = 0; i < nums.size(); ++i)
	{
		tail->next = new ListNode(nums[i]);
		tail = tail->next;
	}
	
	ListNode* head = dummy->next;
	delete dummy;
	return head;
}

// 辅助函数：打印链表
void printList(ListNode* head)
{
	while (head != nullptr)
	{
		cout << head->val;
		if (head->next != nullptr)
		{
			cout << " -> ";
		}
		head = head->next;
	}
	cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head)
{
	while (head != nullptr)
	{
		ListNode* temp = head;
		head = head->next;
		delete temp;
	}
}

int main()
{
	vector<int> nums = {1, 2, 3, 4};
	ListNode* head = buildList(nums);
	
	cout << "原始链表: ";
	printList(head);
	
	Solution sol;
	ListNode* swapped = sol.swapPairs(head);
	
	cout << "交换后链表: ";
	printList(swapped);
	
	deleteList(swapped);
	
	return 0;
}

